package com.sort;

/**
 * 基数排序
 * <p>
 * 将一组的数据 先按照 低位排序
 * 例:
 * 21 23 45 65 98 78 48 119 95 123 3
 * 第一次: 个位
 * 21 23 123 3 45 65 95 98 78 48 119
 * 第二次: 十位
 * 3 119 21 23 123 45 48 65 78 95 98
 * 第三次: 百位
 * 3 21 23 45 48 65 78 95 98 119 123
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RadixSorting implements Sort{
    public static void main(String[] args) {

        int[] old1 = {1, 5, 6, 8, 9};
        int[] old = {3, 19, 49, 45, 23, 78, 45, 12, 19, 461};

        int len = maxSum(old);
        int[] ints = radixSorting2(old, len);


//        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int anInt : ints) {
            System.out.print(anInt + "\t");
        }
    }






    /**
     * 基数排序
     *
     * @param arr 原始数组
     * @param len 数组中最大的数的长度
     */
    public static int[] radixSorting2(int[] arr, int len) {
        for (int i = 0; i < len; i++) {
            Map<Integer, List<Integer>> map = new HashMap<>();
            // 对数组遍历
            for (int k : arr) {
                if (map.get(((int) (k / Math.pow(10, (i))) % 10)) == null) {
                    List<Integer> list = new ArrayList<>();
                    list.add(k);
                    map.put((int) ((k / Math.pow(10, (i))) % 10), list);
                } else {
                    map.get((int) (k / Math.pow(10, (i))) % 10).add(k);
                }
            }
            arr = toArr(map, arr.length);
        }
        return arr;
    }

    public static int maxSum(int[] arr) {
        int i1 = maxInArr(arr);

        //获取最大的数的位数
        int len = 0;

        while (i1 > 0) {
            i1 = i1 / 10;
            len += 1;
        }
        return len;
    }

    /**
     * 获取最大的数
     * @param arr int数组
     * @return  返回最大的值
     */

    public static int maxInArr(int[] arr) {
        int max = 0;
        for (int j : arr) {
            if (max <= j) {
                max = j;
            }
        }
        return max;
    }

    /**
     * 将map 转化 int[]数组
     * @param map  桶
     * @param len 长度
     * @return int 数组
     */
    public static int[] toArr(Map<Integer, List<Integer>> map, int len) {
        int[] arr = new int[len];
        int i = 0;

        for (Integer key : map.keySet()) {
//            System.out.println("key=" + key + "and value=" + map.get(key));

            for (Integer integer : map.get(key)) {
                arr[i] = integer;
                i++;
            }
        }
        return arr;
    }

    @Override
    public int[] run(int[] arr) {
        int len = maxSum(arr);

        return radixSorting2(arr, len);
    }
}
